public class Cutrod {

    public static int cutrod(Integer[] prices, int length) {
		Integer[] profits = new Integer[length+1];
		profits[0] = 0;
		for (int i = 1; i <= length; i++) {
			int profit = -65535;
			for (int j = 1; j <= i; j++) {
				int tmp = prices[j-1] + profits[i-j];
				if (tmp > profit) {
					profit = tmp;
				}
			}
			profits[i] = profit;
		}
		return profits[length];
	}
	
	public static void main(String[] args) {
        int length = 10;
        // Integer[] prices = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30, 32, 32, 36, 38, 44, 47, 50, 54, 56, 60, 78, 88, 99, 107, 110, 112, 115, 119, 123, 136, 140};
		Integer[] prices = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
		int profit = cutrod(prices, length); 
		System.out.print(profit);
	}
}
